package top.whk0710.java_study;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
 * 工具类
 * */
public final class Utils {
	
	public static int binarysearchKey(List<Integer> nums, int targetNum) {
		int left = 0,right = 0; 
		for (right = nums.size()-1; left!=right;) {
			int midIndex = (right + left)/2;
			int mid = (right - left);
			int midValue = (Integer) nums.get(midIndex);
			if (targetNum == midValue) {
				return midIndex;
			}
			if(targetNum > midValue){
			      left = midIndex;
			}else{
			      right = midIndex;
			}
			if (mid <=1) {
				   break;
			}
		}
		int rightnum = ((Integer) nums.get(right)).intValue();
		int leftnum = ((Integer) nums.get(left)).intValue();
		int index =  Math.abs(leftnum - targetNum) > Math.abs(rightnum -targetNum) ? right : left;
		return index;
	}

	/**
	 * 在String数组中选择m个组合（递归解决）
	 * @param strs 被选择的string数组
	 * @param m 需要选择的数量
	 * @return 组合的String数组
	 */
	public static String[] choose_m_in_n_strings (String[] strs, int m){
		String[] result_old;
		if (m < 1) {
			throw new IllegalArgumentException("m不能小于1");
		} else if (m == 1) {
			result_old = new String[] {""};
		} else {
			result_old = choose_m_in_n_strings(strs, m-1);
		}
		int i = 0;
		String[] result = new String[result_old.length*strs.length];
		for (String temp1 : result_old) {
			for (String temp2 : strs) {
				result[i] = temp1 + temp2;
				i++;
			}
		}
		return result;
	}
	
	/**
	 * 求T数组的组合：Cn^m
	 * @param <T> 泛型，传入要求组合的数据类型
	 * @param arr 数组
	 * @param m m
	 * @return 返回所有长度为m的不重复（1,2 和 2,1 算重复）的线性表。
	 * */
	public static <T> ArrayList<ArrayList<T>> combination(T[] arr, int m){
		if(arr.length < 1 || m < 1) throw new IllegalArgumentException("length smaller than 1");		
		return Combination(arr,arr.length,m,new ArrayList<T>());
	}
	
	public static <T> ArrayList<ArrayList<T>>  Combination(T[] A,int n,int m,ArrayList<T> t){
		ArrayList<ArrayList<T>> res=new ArrayList<ArrayList<T>>();
		if(m==0){
			ArrayList<T> temp=new ArrayList<T>(t);
			res.add(temp);
			return res;
		}
		else{	
			for(int i=A.length-n;i<=A.length-m;i++){
				t.add(A[i]);
				res.addAll(Combination(A,A.length-i-1,m-1,t));
				t.remove(t.size()-1);
			}
			return res;
		}
	}
	
    /**
     * 通过循环解决数组全部非降序子集问题
     * @param nums: A set of numbers
     * @return: A list of lists
     */
	public static List<List<Integer>> subsets(int[] nums) {
    	int len = nums.length;
        int count = 1 << len;//利用位操作来计算幂，速度更快
        List<List<Integer>> result = new ArrayList<List<Integer>>(count);
        for (int i = 0; i < count; i++) {
        	List<Integer> temp = new ArrayList<Integer>();
        	for (int j = 0; j < len; j++) {
        		if ((i >>> j) % 2 == 1) {
        			temp.add(nums[j]);
        		}
        	}
        	Collections.sort(temp);
        	result.add(temp);
        }
        return result;
    }
	
	/**
	 * 通过循环解决SET集合全部子集问题
	 * @param s
	 * @return
	 */
	public static List<Set<Integer>> allSubSet (Set<Integer> s) {
    	int len = s.size();
    	List<Integer> sl = new ArrayList<Integer>(s);
        int count = 1 << len;//利用位操作来计算幂，速度更快
        List<Set<Integer>> result = new ArrayList<Set<Integer>>();
        for (int i = 0; i < count; i++) {
        	Set<Integer> temp = new HashSet<Integer>();
        	for (int j = 0; j < len; j++) {
        		if ((i >>> j) % 2 == 1) {
        			temp.add(sl.get(j));
        		}
        	}
        	result.add(temp);
        }
        return result;
	}
	
	/**
	 * 求出指定范围的子集
	 * @param s
	 * @param size:指定的范围
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static Set subSet (Set s, int size) {
		if (s.size() == 0) return Collections.EMPTY_SET;
		int realSize = (s.size() > size? size: s.size());
		Set subSet = new HashSet(realSize);
		Iterator it = s.iterator();
		for (int i = 0; i < realSize; i++) {
			subSet.add(it.next());
		}
		
		return subSet;
	}
	
	/**
	 * 判断一个数是否是理想数
	 * @param num 被要求判断的数字
	 * @return 是的话返回true，否则返回false
	 */
	public static boolean isIdealNumber (long num) {
		try {
			long res = 0;
			Set<Long> cyc = new HashSet<Long>();
			while (res != 1) {
				res = 0;
				String str = String.valueOf(num);
				for (int i = 0; i < str.length(); i++) {
					res+= ((Integer.parseInt(str.substring(i, i+1)))*Integer.valueOf(str.substring(i, i+1)));
				}
				System.out.println(res);
				if (cyc.contains(res)) {
					return false;
				} else {
					cyc.add(res);
					num = res;
				}
			}
			return true;
		} catch (Exception e) {
			return false;
		}
	}
	
	/**
	 * 直接插入排序
	 * @param arr 被排序的数组
	 */
	public static void insertSort (int[] arr) {
		for(int i = 1; i < arr.length; i++) {
			int temp = arr[i];
			int j;
			for(j = i-1; j >= 0 && arr[j] > temp; j--) {
				arr[j+1] = arr[j];
			}
			arr[j+1] = temp;
		}
	}
	
	/**
	 * 希尔排序
	 * @param arr 被排序的数组
	 */
	public static void shellSort (int[] arr) {
		int gap = arr.length/2;
		while(gap > 0) {
			for(int i = gap; i < arr.length; i++) {
				int temp = arr[i];
				int j;
				for(j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
					arr[j+gap] = arr[j];
				}
				arr[j+gap] = temp;
			}
			gap = gap/2;
		}
	}
	
	/**
	 * 平方的最大和子序列问题
	 * @param arr
	 * @return
	 */
	public static int maxSubSum2 (int[] arr) {
		int maxSum = 0;
		for(int i = 0; i < arr.length; i++) {
			int theSum = 0;
			for(int j = i; j < arr.length; j++) {
				theSum += arr[j];
				if(theSum > maxSum)
					maxSum = theSum;
			}
		}
		return maxSum;
	}
	
	/**
	 * 递归求解最大和子序列问题
	 * @param arr
	 * @param left
	 * @param right
	 * @return
	 */
	public static int maxSubSum3(int[] arr, int left, int right) {
		int maxResult = 0;
		
		if (left == right) {
			if (arr[left] > maxResult) {
				maxResult = arr[right];
			}
			return maxResult;
		}
		
		int center = (left + right) / 2;
		int leftSum = 0, rightSum = 0;
		leftSum = maxSubSum3(arr, left, center);
		rightSum = maxSubSum3(arr, center+1, right);
		maxResult = ((leftSum > rightSum)? leftSum : rightSum);
		
		int leftBroaderSum = 0, maxLeftBroaderSum = 0, rightBroaderSum = 0, maxRightBroaderSum = 0;
		for(int i = center; i >= left; i--) {
			leftBroaderSum += arr[i];
			if(leftBroaderSum > maxLeftBroaderSum) {
				maxLeftBroaderSum = leftBroaderSum;
			}
		}
		for(int i = center+1; i <= right; i++) {
			rightBroaderSum += arr[i];
			if(rightBroaderSum > maxRightBroaderSum) {
				maxRightBroaderSum = rightBroaderSum;
			}
		}
		if((maxRightBroaderSum+maxLeftBroaderSum) > maxResult) {
			maxResult = maxRightBroaderSum+maxLeftBroaderSum;
		}
		return maxResult;
	}
	
	/**
	 * 线性时间求解最大和子序列问题
	 * @param arr
	 * @return
	 */
	public static int maxSubSum(int[] arr) {
		int maxResult = 0, theSum = 0;
		for(int i = 0; i < arr.length; i++) {
			theSum += arr[i];
			if(theSum > maxResult) {
				maxResult = theSum;
			} else if(theSum < 0) {
				theSum = 0;
			}
		}
		return maxResult;
	}
	
	/**
	 * 递归实现二分查找
	 * @param arr
	 * @param target
	 * @param start
	 * @param end
	 * @return
	 */
	public static int binarySearch(int[] arr, int target, int start, int end) {
		if(start == end) {
			if(arr[end] == target) {
				return end;
			} else {
				return -1;
			}
			
		}
		int mid = (start + end) / 2;
		if(target > arr[mid]) {
			return binarySearch(arr,target,mid+1,end);
		} else if(target < arr[mid]) {
			return binarySearch(arr,target,start,mid);
		} else{
			return mid;
		}
	}
	
	/**
	 * 迭代实现二分查找
	 * @param arr
	 * @param target
	 * @return
	 */
	public static int binarySearch_iter(int[] arr, int target) {
		int start = 0, end = arr.length - 1;
		while(start < end) {
			int mid = (start + end) / 2;
			if(target > arr[mid]) {
				start = mid + 1;
			} else if(target < arr[mid]) {
				end = mid - 1;
			} else{
				return mid;
			}
		}
		return -1;
	}
	
	/**
	 * 利用欧几里得算法求救最大公因数
	 * @param bigger
	 * @param smaller
	 * @return
	 */
	public static long gcd(long bigger, long smaller) {
		if(bigger < smaller) {long temp = smaller; smaller = bigger; bigger = temp;}
		while (smaller != 0) {
			long rem = bigger % smaller;
			bigger = smaller;
			smaller = rem;
		}
		return smaller;
	}
	
	/**
	 * 利用迭代（或递归）快速求解幂运算
	 * @param m
	 * @param n
	 * @return
	 */
	public static long pow(long m, int n) {
/*		if(n == 0) return 1;
		if(n == 1) return m;
		if(n % 2 == 0) {
			return pow(m*m, n/2);
		} else {
			return pow(m*m, n/2) * m;
		}*/
		long result = 1;
		if(n % 2 == 1) result *= m;
		while(n > 1) {
			result *= m*m;
			n = n/2;
		}
		return result;
	}
	
	/**
	 * 递归列出指定目录下的所有
	 * @param depth
	 * @param file
	 */
	public static void listAllFile(int depth, File file){
		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < depth; i++){
			sb.append("  ");
		}
		sb.append(file.getName());
		System.out.println(sb);
		if(file.isDirectory()){
			for(File f : file.listFiles()){
				listAllFile(depth+1,f);
			}
		}
		
	}
}
